﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
//给你两个单链表的头节点 headA 和 headB ，
//请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
//图示两个链表在节点 c1 开始相交：
//
//题目数据 保证 整个链式结构中不存在环。
//
//注意，函数返回结果后，链表必须 保持其原始结构 。
//
//
//评测系统 的输入如下（你设计的程序 不适用 此输入）：
//
//intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
//listA - 第一个链表
//listB - 第二个链表
//skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
//skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
//评测系统将根据这些输入创建链式数据结构，
//并将两个头节点 headA 和 headB 传递给你的程序。
//如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
//
//输入：intersectVal = 8, listA = [4, 1, 8, 4, 5], 
//listB = [5, 6, 1, 8, 4, 5], skipA = 2, skipB = 3
//输出：Intersected at '8'
//解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
//从各自的表头开始算起，链表 A 为[4, 1, 8, 4, 5]，链表 B 为[5, 6, 1, 8, 4, 5]。
//在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。


 
  struct ListNode {
      int val;
      struct ListNode *next;
  };
 
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* curA = headA;
    int k = 0;
    int* ar = (int*)malloc(30000 * sizeof(int));
    while (curA) {
        ar[k++] = curA->val;
        curA->val = -1;
        curA = curA->next;
    }
    struct ListNode* curB = headB;
    while (curB && curB->val != -1) {
        curB = curB->next;
    }
    curA = headA;
    int i = 0;
    while (curA) {
        curA->val = ar[i++];
        curA = curA->next;
    }
    return curB;
}
//
//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 
// 如果链表无环，则返回 null。
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，
// 则链表中存在环。 为了表示给定链表中的环，
// 评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
// 如果 pos 是 - 1，则在该链表中没有环。注意：pos 不作为参数进行传递，
// 仅仅是为了标识链表的实际情况。
//不许修改 链表。
//输入：head = [3, 2, 0, -4], pos = 1
//输出：返回索引为 1 的链表节点
//解释：链表中有一个环，其尾部连接到第二个节点。


  struct ListNode {
      int val;
      struct ListNode *next;
  };
 
struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {

            fast = head;
            while (fast != slow)
            {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    }
    return NULL;
}